Workload scheduling is an increasingly important component of IT (Information Technology) environments. Indeed, many grid computing environments are driven by the scheduling of work across a distributed set of resources (e.g. computation, storage, communication capacity, software licenses, special equipment etc.). Most grid systems include a job scheduler, to locate a machine on which to run a job submitted by a user. Simple job schedulers assign jobs to the next available machine whose resources match the needs of the job. However, more advanced schedulers implement a job priority system, wherein jobs with higher priorities are preferentially allocated to grid machines. Schedulers may also implement policies, providing various constraints on jobs, users, and resources (e.g. restricting grid jobs from executing at certain times of the day).
In essence, scheduling is an optimization problem, which is fairly straightforward when only one resource type (e.g. CPU) is involved. Further performance improvements may be achieved by including more resource variables in the scheduling process, the resulting multivariate optimization becomes a difficult mathematics problem. In attempting to simplify the problem, prior art workload distribution algorithms typically assume that the distribution problem is one of deploying substantially homogeneous jobs in a substantially homogeneous environment. Thus, these prior art algorithms fail to recognize that different jobs often have different resource requirements. Similarly, prior art algorithms typically fail to recognize the extent to which a given job deployment may influence subsequent jobs, thereby affecting the overall job throughput of a system.